package DataModel.SegmentTree;

import java.util.Stack;

/**
 * Implementation of segment tree preorder iterator
 * @author Guy
 *
 */
public class SegmentTreePreorderIterator implements SegmentTreeIterator {
	Stack<SegmentTreeNode> s = null;
	
	/**
	 * Creates the iterator
	 * @param t - segment tree on which to iterate
	 * @return iterator
	 */
	static public SegmentTreePreorderIterator IteratorInitialize(SegmentTree t) {
		if (t.getRoot()==null) {
			System.err.println("Tree not initialized");
			return null;
		}
		return new SegmentTreePreorderIterator(t.getRoot());
	}
	/**
	 * Creates iterator which will start from specific node
	 * @param n start node
	 * @return iterator
	 */
	static public SegmentTreePreorderIterator IteratorInitialize(SegmentTreeNode n) {
		if (n ==null) {
			System.err.println("Tree not initialized");
			return null;

		}
		return new SegmentTreePreorderIterator(n); 
	}
	
	/**
	 * Create new iterator from start node
	 * @param start start node
	 */
	SegmentTreePreorderIterator(SegmentTreeNode start) {
		this.s = new Stack<SegmentTreeNode>();
		s.push(start);
		
	}
	
	/**
	 * Next tree node pointed by iterator
	 * @return next tree node
	 */
	public SegmentTreeNode next() {
		if (s.empty()) return null;
		
		SegmentTreeNode res = s.pop();
		if (res.rightSon() != null ) {
			s.push(res.rightSon());
			
		}
		if (res.leftSon()  != null ) {
			s.push(res.leftSon());
		}
		
		return res;
	}
	/**
	 * Returns true if unvisited node exists
	 */
	public boolean hasNext() {
		return !s.isEmpty();
	}
}
